package DisjointSetUnion;

/**
 * 情侣牵手
 * n对情侣坐在连续排列的2n个座位上，想要牵到对方的手
 * example: [0,1,2,4,3,5] -> 配对后 [0,1,2,3,4,5]
 * 等价与换几次原数组有序
 */
public class CouplesHoldingHands {
    public static void main(String[] args) {
        System.out.println(minSwapsCouples(new int[]{0, 1, 2, 4, 3, 5}));
    }

    public static int minSwapsCouples(int[] row) {
        int n = row.length;
        build(n / 2);
        for (int i = 0; i < n; i += 2) {
            union(row[i] / 2, row[i + 1] / 2);
        }

        // 需要交换的次数 = 对数 - 并查集的集合数量
        return n / 2 - sets;
    }

    // 最多30队情侣
    public static int MAX_N = 31;

    public static int[] ancestor = new int[MAX_N];

    // 并查集里面有几个集合
    public static int sets;

    public static void build(int m) {
        for (int i = 0; i < m; i++) {
            ancestor[i] = i;
        }

        sets = m;
    }

    public static int find(int i) {
        if (i != ancestor[i]) {
            ancestor[i] = find(ancestor[i]);
        }
        return ancestor[i];
    }

    public static void union(int x, int y) {
        int ax = find(x);
        int ay = find(y);

        if (ax != ay) {
            ancestor[ax] = ay;
            // 合并两个集合，所以集合数量-1
            sets--;
        }
    }
}
